package org.example.algorithm.sort;

//75. 颜色分类
public class SortColorsSolution {

    public static void main(String[] args) {
        int[] nums = {2,0,2,1,1,0};
        SortColorsSolution solution = new SortColorsSolution();
        solution.sortColors(nums);
        for (int i=0;i<nums.length;i++) {
            System.out.println(nums[i]);
        }
    }

    //单指针
    //两次遍历，第一次把所有0移到开头，第二次把所有的1移到紧挨的位置
    public void sortColors(int[] nums) {
        int left = 0;
        for (int i=0;i<nums.length;i++) {
            if (nums[i] == 0) {
                swap(nums, i, left);
                left++;
            }
        }
        for (int i=left;i<nums.length;i++) {
            if (nums[i] == 1) {
                swap(nums, i, left);
                left++;
            }
        }
    }

    //使用三指针
    //输入：nums = [2,0,2,1,1,0]
    //输出：[0,0,1,1,2,2]
    public void sortColors2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[left] == 0) {
                left++;
                continue;
            }
            if (nums[right] == 2) {
                right--;
                continue;
            }
            int cur = left;
            while (cur <= right && nums[cur] == 1) {
                cur++;
            }
            if (cur > right) {
                break;
            }
            if (nums[cur] == 2) {
                swap(nums, cur, right);
                right--;
            } else {
                //==0
                swap(nums, cur, left);
                left++;
            }
        }

    }

    //推荐（定义循环不变量）
    public void sortColors3(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        //定义循环不变量
        //[0, left) 0
        //[left, i) 1
        //(right, len-1] 2
        int left = 0;
        int i=0;
        int right = len-1;
        while (i<=right) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 0) {
                swap(nums, i, left);
                left++;
                i++;
            } else {
                swap(nums, i, right);
                right--;
            }
        }
    }

    private void swap(int[] nums, int from, int to) {
        int temp = nums[from];
        nums[from] = nums[to];
        nums[to] = temp;
    }
}
